package com.cat.recursion;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/sudoku-solver/?envType=daily-question&envId=2025-08-31
 * @create 2025/8/31 09:38
 * @since JDK17
 */

public class Solution01 {
    char[][] s;
    int n, m;
    boolean[][] row = new boolean[9][9], col = new boolean[9][9], grid = new boolean[9][9];
    public void f(int i, int j) {
        int ni = i, nj = j;
        if (j < 8) {
            nj++;
        } else {
            ni++;
            nj = 0;
        }
        if (s[i][j] == '.') {
            for (int l = 0; l < 9; l++) {
                if (!row[i][l] && !col[j][l] && !grid[i / 3 + j / 3][l]) {
                    s[i][j] = ((char) (l + '1'));
                    row[i][l] = true;
                    col[j][l] = true;
                    grid[i / 3 + j / 3][l] = true;
                    f(ni, nj);
                    row[i][l] = false;
                    col[j][l] = false;
                    grid[i / 3 + j / 3][l] = false;
                }
            }
        } else {
            f(ni, nj);
        }
    }
    public void solveSudoku(char[][] board) {
        s = board;
        n = s.length;
        m = s[0].length;
        // 先将之前有过的都标记起来
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char a = s[i][j], b = s[j][i], c = s[i / 3 * 3 + j / 3][j % 3 + i % 3 * 3];
                if (a != '.') {
                    row[i][a - '1'] = true;
                }
                if (b != '.') {
                    col[i][b - '1'] = true;
                }
                if (c != '.') {
                    grid[i][c - '1'] = true;
                }
            }
        }
        f(0, 0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(s[i][j] + " ");
            }
            System.out.println();
        }
    }
}
